package com.smh;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @author shiminghui
 * @date 2025/3/18 14:35
 * @description: n对括号组合, 有多少种组合方法
 */
public class _063_括号组合 {

    @Test
    public void test() {
        count(4);
    }


    /**
     * 使用Catalan 数列求解
     */
    public void count(int n) {
        ArrayList[] dp = new ArrayList[n + 1];
        for (int i = 0; i < dp.length; i++) {
            dp[i] = new ArrayList<String>();
        }
        dp[0].add("");
        dp[1].add("()");
        // dp[2] = [()(),(())]
        // dp[3] = [()()(), ()(()), (())(), (()()), ((()))]
        for (int i = 2; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                ArrayList<String> k1 = dp[j];
                ArrayList<String> k2 = dp[i - j - 1];
                for (String s1 : k1) {
                    for (String s2 : k2) {
                        dp[i].add("(" + s1 + ")" + s2);
                    }
                }
            }
        }
        print(dp);
    }

    private void print(ArrayList<String>[] arr) {
        for (ArrayList<String> list : arr) {
            System.out.println(list.toString());
        }
    }

}
